#ifndef TRIE_H
#define TRIE_H
#include <bits/stdc++.h>
using namespace std;

template<typename T>
struct Trienode {
    T value;
    Trienode *next[300];

    Trienode() {
        for(int i = 0; i < 300; i++) next[i] = nullptr;
    }

    Trienode(T temp) {
        this->value = temp;
        for(int i = 0; i < 300; i++) next[i] = nullptr;
    }
};

class Trie
{
    public:
        Trie();

        ~Trie();

        string search(string key);

        void insert(string key, string value);

        void clear(Trienode<string>* root);

        void deleteNode(string key);

    private:
        Trienode<string>* root;

        Trienode<string>* search(Trienode<string>* u, string key, int d);

        Trienode<string>* insert(Trienode<string>* u, string key, int d, string value);

        void deleteNode(Trienode<string>* &u, string key, int d);
};

#endif // TRIE_H


